# 解法 2 的 dp 写法
class Solution:
    def __init__(self):
        self.cache = {}

    def uniquePaths(self, m: int, n: int) -> int:
        for x in range(m):
            for y in range(n):
                c = (x, y)
                if x == 0 or y == 0:
                    self.cache[c] = 1
                else:
                    self.cache[c] = self.cache[(x - 1, y)] + self.cache[(x, y - 1)]
        return self.cache[(m - 1, n - 1)]


solu = Solution()
print(solu.uniquePaths(3, 2))